1. Field of the Invention
The invention relates generally to electronic logic circuitry and, more particularly, to a device and method for detecting digital data and prioritizing that data in connection with cache memory operation in computers.
2. Description of the Related Art
An electronic logic circuit is a network of electrical connections and logic elements that performs one or more specified logical functions. Electronic logic circuits may perform a variety of operations and serve in diverse applications. Logic circuits may operate according to digital or analog principles depending upon design. In the presently available digital computers, numerous and varied logic circuitry is employed in central processing units and other hardware to accomplish desired manipulation of digital data. One particular application for electronic logic circuitry in a digital computer may be in manipulating and performing operations with data stored in memory, for example, data stored in cache memory, of the computer.
It may be desirable in certain digital electronic applications to, at times, observe a substantial number of stored data locations, or "cells". In those applications, it may also be desirable to perform one or more tasks based on the status of the cells observed, for example, depending on which cells, if any, have been modified. When it is detected that particular cells have been modified in those instances, it may be desired that more than one task (i.e., data manipulation operation) be performed. It is also possible in those applications that the tasks, and sequences thereof, be conducted in a particular instance as dictated by the particular cells (or statuses thereof, such as whether modified or unmodified) that are observed.
In the situation where a substantially large number of memory data cells must be observed and a sequence of multiple tasks performed as dictated by the particular cells, the prior electronic logic circuitry has typically operated by observing each individual cell of the large number of cells in a stepped manner. In that operation, a first cell is observed, then a task may be performed based on that observation. After the task relative to the first cell is performed, a next cell is observed and, if appropriate according to design, a task then performed based on that next cell. This stepped observation of cells has then been repeated in the prior art devices until all cells of the large number of cells have been observed and appropriate tasks dictated thereby performed.
As may be understood, this stepped observance of each cell of a large number of memory cells followed by a task may take significant processing time. A device and method which circumvents this stepped approach of the prior art would clearly be an improvement in the art. The present invention provides just such an improvement. One application for the invention, as hereafter described, is in memory storage operations in digital computers. In particular, the invention is particularly suited to those digital computers having a cache memory, as also hereafter described.
Today's computers and other digital processing devices often employ cache memories. A cache memory is typically considered a temporary memory, that is, a memory that is utilized only for temporary storage of data. Cache memories may store data temporarily for a variety of purposes, including to make data that is often needed readily available to circuitry that manipulates the data. By making such data so available to circuitry, fetch and store times for circuitry operation may be speeded. Cache memory is thus thought of as fast memory used in devices to optimize speed and performance.
In many applications, cache memories serve to speed the average memory access time of devices, such as digital computers, which require significant amounts of memory storage. Because significant memory storage is required by those devices, memory must be employed that is not closely associated with a processor or other logic circuitry. This memory is referred to as "external" memory because it is located off the device containing the logic circuitry and so must be accessed by system buses when data from that memory is to be manipulated or otherwise used by the logic circuitry. In these instances where external memory is necessary, the time required for logic circuitry to access the memory through system buses may be significant, resulting in slow operation of the device. Cache memories may be employed with these devices in many instances to speed operation of the devices.
As mentioned, cache memory is typically temporary memory. Because temporary, cache memory often is not quite so large as external memory in terms of number of memory cells. Because not so large as external memory, cache memory may be associated relatively closely with logic circuitry. This close association and smaller size of cache memory allows for easier and faster access of cache memory than of external memory. Cache memory, however, generally will not store as much data as external memory because of the smaller size of cache memory. Nevertheless, it is desirable for logic circuitry to be able to use data stored in the larger external memory. Cache memory may be employed in many instances to store desired information from external memory, thus, allowing logic circuitry to access cache memory to thereby obtain data (albeit indirectly) from external memory.
As may be anticipated, many factors impact the storage and access effectiveness of cache memory, for example, cache size, cache physical organization, cache line replacement/modification algorithms, and the behavior of any software being run which employs the cache memory. In typical operation of a cache memory, the cache memory maintains a copy of the most recently used code or data retrieved from the external memory. This code or data held in cache memory is what is used by the logic circuitry in its iterative operations. In devices utilizing cache memory, external memory has typically been employed only for permanent (or extended) data storage and is typically not accessed directly by the logic circuitry. Rather, the logic circuitry accesses cache memory, which cache memory holds data retrieved from external memory and then temporarily stored in cache for manipulation by the logic circuitry.
Because the logic circuitry of these devices manipulates data held in cache memory rather than data retrieved directly from external memory, it is important that cache memory hold, from time to time, appropriate data from the external memory for logic circuitry operation and that external memory hold, from time to time, appropriate data then held in cache memory. Though data for manipulation may be stored in cache memory, the data must at times nevertheless correctly reflect the desired permanent (or extended) storage data then held in external memory. Therefore, data stored in cache memory, though temporary and almost continuously changing, must from time to time be identical to appropriate data then stored in external memory. Because cache memory must so reflect appropriate data held in external memory, and vice versa, old data held in cache memory must frequently be replaced with appropriate new data from external memory and old data held in external memory must frequently be replaced with appropriate new data from cache memory.
There are a number of known procedures and devices for replacing old data in external memory with appropriate new data from cache memory. In those procedures and devices, it is generally the case that a determination is made that data in cache memory has been modified, then those modifications are written to external memory. These procedures, and their effectiveness, for replacing old data with new data are generally dependent upon cache organization and the other factors previously described with respect to cache effectiveness.
Regardless of organization and other factors, however, prior procedures for determining modifications of cache and writing cache modifications to external memory have required a stepped check, as previously described herein, through each location of stored information in the cache to determine at each location whether there has been any modification of cached data. Only when a modification is found in that stepped check is the external memory updated. Because cache memory is being replaced continually during the operation of associated logic circuitry, these prior procedures of stepping through every piece of information stored in the cache until a modification is found are time consuming relative to logic circuit operations. It would, therefore, be an advantage over the prior art if new devices and procedures were developed for identifying modifications of cache and updating external memory to reflect those modifications, which devices and procedures would allow reduced cache memory operation times.
In discussion of cache memories as they may relate to the priority lookahead encoder invention described herein, a number of particular terms are often used. For a better understanding of the objects and advantages of the present invention, definitions are provided here for certain of those terms as follows:
Associativity--a number which refers to the number of possible locations in the cache based on cache organization in which a specific address may be cached. It also refers to the number of tags which are read and compared concurrently.
Clean line--a cache line that is not marked as modified because it is not written to main memory in a copyback write policy. The fact that such a cache line is not marked as modified indicates that the line is not modified relative to the relevant main memory.
Copyback--a write policy in which a write-back is performed in the cache when data is modified within the cache. When cached data is modified, the cache is flushed. When flushed, the data in the line or lines of the cache then marked as modified is written (copied back) to the main memory.
Data array--a random access memory array that contains the data variables for use by a processor.
Data cache--a cache which is used for caching frequently used processor data variables.
Index--each cache line has an index associated with it that must be stored and compared against the index of the memory request. Indexes are kept as entries (one per line) in a directory that establishes the correspondence between the data in the cache and the particular fragment of main memory that is represented.
Line (or Block)--a cache line or block is a group of sequential words in cache memory associated with a tag.
Look-up--a look-up is performed when some data is pulled from the main memory and placed in the cache.
Modified line--a cache line is marked as modified when it is written in a copyback write policy. The mark indicates that the line contains the most recent version of the data.
Status Bits--a status bit is associated with each cache line and indicates the modified or unmodified status of the line.
Tag--the tag identifies the address of the data or instruction which is currently present in the cache. A cache tag is associated with each cache line and is stored in the tag array.
Tag array--a random access memory array that contains the address tags for cache data.
The present invention in a preferred embodiment is a priority lookahead encoder with associativity determination logic. The priority lookahead encoder may have varied application, such as in any instance where observance of a significantly large amount of data is required and where multiple tasks may be necessary in response to the data observed. A particularly useful application of the invention, however, is in digital computers having cache memory. As will be more fully discussed herein, the present invention provides a speeded mechanism and procedure for simultaneously observing large amounts of data and performing tasks dictated by the data. The invention provides these advantages because it prioritizes the performance of tasks dictated by observed data, therefore, allowing for substantially simultaneous observance of large amounts of data. Thus, the invention is a significant improvement in the art.